Coding systems using cyclic redundancy check (CRC) techniques are readily implemented yet provide powerful error detection capabilities. Accordingly, CRC techniques are widely used in, for example, disk controllers, Internet protocols such as such as IP and iSCSI, and other networking protocols including ethernet. In the CRC technique, a block of d data bits denoted as a frame is joined with an extra block of m bits called the frame check sequence (FCS). Just like a checksum such as a parity bit, the FCS introduces redundancy into the transmitted (d+m) bit codeword that permits the receiver to detect errors. All the bits are treated as binary coefficients of polynomials. A receiver will detect errors in the received (d+m) bit codeword by dividing (using polynomial arithmetic) the codeword with a generator polynomial. If the remainder from this division is zero, a CRC-enabled receiver will assume that the transmitted codeword contains no errors.
As discussed above, certain Internet protocols require CRC coding to provide error detection. In these protocols, data may be packetized or divided into sub-messages for transmission. For example, an iSCSI data word may be protected with its CRC FCS and transmitted via multiple IP packets (which may be denoted as sub-messages) that may arrive in any order. The CRC coding of the FCS, however, is based on the original data word and not the IP packets/sub-messages. Conventionally, a receiver may perform a CRC calculation on the resulting sub-messages in one of two approaches. In a first approach to perform the CRC division/calculation, a conventional receiver could accumulate the sub-messages to reconstruct the message and divide the message by the generator polynomial. If the remainder from this division is zero, the message is assumed to be error free. Because the CRC division is performed after all the sub-messages have been received, there is extra latency causing undesirable delay. In addition, the receiver must have read access to the memory storing the accumulated sub-messages. Even if such memory access is practical, the extra loading on the memory bus further impacts system performance.
Alternatively, in a second approach to perform the CRC calculation, a receiver could compute the CRC remainder by performing a CRC division on each sub-message as it arrives in order using a CRC computation engine. In sequence processing of the sub-messages is required to ensure that the CRC computation engine has the proper initial state. The processed sub-messages could then be delivered to a remote memory not accessible to the CRC computation engine, eliminating the loading on the memory bus suffered by the previous approach. However, because the second approach requires in sequence delivery of the sub-messages, it cannot be applied where support of out of order sub-message delivery is required or desired.
Accordingly, there is a need in the art for a CRC computation technique that calculates the CRC of sub-messages regardless of arrival order.